//
// Description: 146. LRU 缓存
// Created by Loading on 2022/9/11.
//

#include <bits/stdc++.h>

using namespace std;

struct LinkedNode {
    int key, value;
    LinkedNode *pre, *next;
    LinkedNode() : key(-1), value(-1), pre(nullptr), next(nullptr) {}
    LinkedNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    explicit LRUCache(int capacity) {
        this->capacity = capacity;
        head = new LinkedNode;
        tail = new LinkedNode;
        head->next = tail;
        tail->pre = head;
    }

    int get(int key) {
        if (m.find(key) != m.end()) {
            moveToHead(m[key]);
            return m[key]->value;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        if (m.find(key) != m.end()) {
            moveToHead(m[key]);
            m[key]->value = value;
        } else {
            ++size;
            // 超出最大容量，移除队尾
            if (size > capacity) {
                auto node = tail->pre;
                m.erase(node->key);
                removeNode(node);
                delete node;
                --size;
            }
            m[key] = new LinkedNode(key, value);
            addToHead(m[key]);
        }
    }

private:
    // 添加节点至队头
    void addToHead(LinkedNode *node) {
        node->next = head->next;
        node->next->pre = node;
        head->next = node;
        node->pre = head;
    }

    // 移除节点
    void removeNode(LinkedNode *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    // 将节点移至队头
    void moveToHead(LinkedNode *node) {
        removeNode(node);
        addToHead(node);
    }

private:
    LinkedNode *head, *tail;
    unordered_map<int, LinkedNode *> m;
    int size = 0;
    int capacity;
};

int main() {
    auto lRUCache = new LRUCache(2);
    lRUCache->put(1, 1);
    lRUCache->put(2, 2);
    cout << lRUCache->get(1) << endl;
    lRUCache->put(3, 3);
    cout << lRUCache->get(2) << endl;
    lRUCache->put(4, 4);
    cout << lRUCache->get(1) << endl;
    cout << lRUCache->get(3) << endl;
    cout << lRUCache->get(4) << endl;

    return 0;
}